問題文

頂点$n$からなる木が与えられる。
頂点には番号$i (0 \leq i < n)$がついている。根は$0$である。
辺には番号$i (0 \leq i < n-1)$がついており、辺$i$は頂点$a_i$と頂点$b_i$を繋ぐ。

各辺$i$には、$2 \times 2$行列$X_i (0 \leq i < n-1)$が載っている。$X_i$の初期値は単位行列である。

以下のクエリを$q$個処理せよ。
(1) 変更クエリx
x $i\ x_{00}\ x_{01}\ x_{10}\ x_{11}$
$X_i (0 \leq i < n-1)$を$\begin{pmatrix} x_{00} & x_{01} \\ x_{10} & x_{11}\end{pmatrix}$に変更する。
(2) 取得クエリg
g $i\ j$
頂点$i$は頂点$j$の先祖であることが保証される。
頂点$i$から頂点$j$へのパスの辺に載っている行列を、すべて掛けた行列の各要素を$10^9+7$で割った出力する。
根側が左、葉側が右になるほうにかける。

入力

$n$
$a_0\ b_0$
$a_1\ b_1$
$\vdots$
$a_{n-2}\ b_{n-2}$
$q$
$query_1$
$\vdots$
$query_q$

入力は全て整数。

$2 \leq n \leq 100000$
$1 \leq q \leq 20000$

クエリx
$0 \leq i < n-1$
$0 \leq x_{st} \leq 1000$

クエリg
$0 \leq i, j < n$

クエリgが$1$個以上あることが保証される。

出力

答えが$\begin{pmatrix} c_{00} & c_{01} \\ c_{10} & c_{11}\end{pmatrix}$であれば、
$c_{00}\ c_{01}\ c_{10}\ c_{11}$の順番で一行で出力せよ。

サンプル

6
0 1
1 3
0 2
2 4
2 5
8
x 2 1 3 0 2
x 3 6 2 8 7
g 0 2
g 0 4
g 0 5
g 2 5
x 4 7 2 4 9
g 0 5

1 3 0 2
30 23 16 14
1 3 0 2
1 0 0 1
19 29 8 18